package threshold;

import java.util.HashMap;
import java.util.Map;

public class LongestPalindrome {

    public String longestPalindrome1(String s) {
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i <s.length(); i++) {
            for (int j = i; j <s.length() ; j++) {
                String substring = s.substring(i, j + 1);
                //判断subString是否是回文字符串
                if(isPalindrome1(substring)){
                    map.put(substring,substring.length());
                }
                
            }
        }
        int max = 0;
       String maxString = "";
        for(Map.Entry<String,Integer> entry: map.entrySet()){
            String key = entry.getKey();
            Integer value = entry.getValue();
            if(value>max){
                max = value;
                maxString = key;
            }
        }
        return maxString;
    }
    public boolean isPalindrome1(String s){
        for (int i = 0,j=s.length()-1; i < j; i++,j--) {
            if (s.charAt(i)!=s.charAt(j)){
                return false;
            }
        }
        return true;
    }

    public String longestPalindrome(String s){

        if(s.length()==1){
            return s;
        }
        int maxLen = 1;
        int begin =0;
        for (int i = 0; i < s.length()-1; i++) {
            for (int j = i+1; j <s.length() ; j++) {
                if(j-i+1>maxLen && isPalindrome(s,i,j)){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
    public boolean isPalindrome(String s,int left,int right){
        for (int i = left,j=right; i < j; i++,j--) {
            if (s.charAt(i)!=s.charAt(j)){
                return false;
            }
        }
        return true;
    }


    public String longestPalindromeDp(String s){

        int len = s.length();
        if(len==1){
            return s;
        }
        int maxLen =1;
        int begin = 0;
        //定义并初始化动态数组
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i <len ; i++) {
            dp[i][i] = true;
        }
        //填写dp数组，利用动态规划求解
        for (int j = 1; j <len ; j++) {
            for (int i = 0; i < j; i++) {
                if(s.charAt(i)!=s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    if(j-i<3){
                        //i,j指向的的元素相等，并且s(i,j)的长度为2或者三说明字串一定回文
                        //i，j也是回文
                        dp[i][j] = true;
                    }else {
                        //i,j相等并且长度过长时
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if((j-i+1)>maxLen && dp[i][j]){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
    public static void main(String[] args) {
        LongestPalindrome test = new LongestPalindrome();
        String s = "babad";
        System.out.println(test.longestPalindromeDp(s));
    }
}
